<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>前序遍历</title>
</head>

<body>
    <script>
        function Node(data, left, right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        Node.prototype = {
            show: function() {
                console.log(this.data);
            }
        }

        function Tree() {
            this.root = null;
        }

        Tree.prototype = {
            insert: function(data) {
                var node = new Node(data, null, null);
                if (!this.root) {
                    this.root = node;
                    return;
                }
                var current = this.root;
                var parent = null;
                while (current) {
                    parent = current;
                    if (data < parent.data) {
                        current = current.left;
                        if (!current) {
                            parent.left = node;
                            return;
                        }
                    } else {
                        current = current.right;
                        if (!current) {
                            parent.right = node;
                            return;
                        }
                    }

                }
            }
        }

        var bTree = new Tree();
        bTree.insert(3);
        bTree.insert(8);
        bTree.insert(1);
        bTree.insert(2);
        bTree.insert(5);
        bTree.insert(7);
        bTree.insert(6);
        bTree.insert(0);


        /*

                    3
                  /   \
                 1     8
                / \   / 
               0   2  5 
                      \
                       7
                      /
                     6  

        */


        /** 递归 */
        var preorderTraversal = function(root, array = []) {
            if (root) {
                array.push(root.data);
                preorderTraversal(root.left, array);
                preorderTraversal(root.right, array);
            }
            return array;
        };

        // 测试递归
        var pt = preorderTraversal(bTree.root)
        console.log('递归遍历结果：')
        console.log(pt)

        /** 非递归 */
        var preorderTraversal = function(root) {
            const result = [];
            const stack = [];
            let current = root;
            while (current || stack.length > 0) {
                while (current) {
                    result.push(current.data);
                    stack.push(current);
                    current = current.left;
                }
                current = stack.pop();
                current = current.right;
            }
            return result;
        };

        // 测试非递归
        var pt = preorderTraversal(bTree.root)
        console.log('非递归遍历结果：')
        console.log(pt)
    </script>
</body>

</html>